package test.day06;

import java.util.Arrays;

public class LongestIncreaseSubArray {
	public int lengthOfLIS(int[] nums) {
		int[] res = new int[nums.length];
		int len = 0;
		for (int num: nums) {
			int idx = Arrays.binarySearch(res, 0, len, num);
			idx = idx < 0 ? -idx - 1: idx;
			res[idx] = num;
			if (idx == len) {
				len++;
			}
		}
		return len;
	}

	public int lengthOfLIS1(int[] nums) {
		int[] dp = new int[nums.length];
		for(int i = 0; i < nums.length; i++){
			dp[i] = 1;
			for(int j = 0; j < i; j++) {
				if(nums[j] < nums[i]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
		}
		int ret = 1;
		for(int i = 0; i < dp.length; i++){
			ret = Math.max(ret, dp[i]);
		}
		return ret;
	}

	public int lengthOfLIS2(int[] nums) {
		int[] dp = new int[nums.length];
		dp[0] = 1;
		int res =1;
		for(int i=1;i<nums.length;i++){
			dp[i] = 1;
			for(int j=0;j<i;j++){
				if(nums[i]>nums[j]){
					dp[i]=Math.max(dp[i],dp[j]+1);
				}

			}
			res = Math.max(res,dp[i]);
		}
		return res;
	}



	public static void main(String[] args) {
		int[] num = new int[]{10,9,2,5,3,7,101,18};
		LongestIncreaseSubArray longestIncreaseSubArray = new LongestIncreaseSubArray();
		System.out.println(longestIncreaseSubArray.lengthOfLIS1(num));
	}
}
